package com.ztl.leetcode.SwordFingerOffer;

import java.util.Arrays;

/**
 * @author @ztl
 * @ClassName:MergeInterval_56
 * @Package:com.ztl.leetcode.SwordFingerOffer
 * @date 2023年05月31日 16:01
 * @description:以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间.
 * @version: 1.0
 */
public class MergeInterval_56 {
    //排序O(log n) 遍历数组合并区间O(n) 总体时间复杂度O(n log n)，排序加上合并区间空间复杂度 O(log n)
    public int[][] merge(int[][] intervals) {
        //思路：对区间集合排序，排序规则为：每个区间的第一个元素升序
        //把排序后的区间集合从左到右逐个添加
        //添加规则：1.待添加区间的左元素>已添加的最后一个区间的最后一个元素
        //          2.待添加区间的左元素<=已添加的最后一个区间的最后一个元素
        //根据以上两种情况，使用两种处理方法
        //情况1：待添加区间直接加入
        //情况2：修改已添加的最后一个区间的最后一个元素=待添加右元素和已添加最后一个右元素的最大值

        //验证：规则1：待添加元素肯定不在已添加的集合内
        //规则2：待添加元素与已添加的最后一个元素重合，第一个元素因为升序排序不需要修改，最后一个元素修改成最大的即可
        //如此遍历添加，可以确保每个待添加的元素只可能与已添加的最后一个元素存在重复区间

        // 对区间集合排序，排序规则为：每个区间的第一个元素升序
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        // 遍历区间
        int[][] res = new int[intervals.length][2];
        int idx = -1;
        for (int[] interval : intervals) {
            //如果结果数组是空的，待添加区间的左元素>已添加的最后一个区间的最后一个元素
            //待添加区间直接加
            if (idx == -1 || interval[0] > res[idx][1]) {
                res[++idx] = interval;
            } else {
                //待添加区间的左元素<=已添加的最后一个区间的最后一个元素
                //修改已添加的最后一个区间的最后一个元素=待添加右元素和已添加最后一个右元素的最大值
                res[idx][1] = Math.max(res[idx][1], interval[1]);
            }
        }
        return Arrays.copyOf(res, idx + 1);
    }
}
